# encoding=utf-8

from search import Node, FIFOQueue
from tree_search import TreeSearch
from window import ScrolledText,INSERT,END


class BFS(ScrolledText):
	def __init__(self, problem,model='graph',scrolledtext=None):
		self._problem = problem
		self._model = model
		self._scrolledtext=scrolledtext
	def execute(self):
		if self._model == 'tree':
			tree_search = TreeSearch(self._problem, FIFOQueue())
			result = tree_search.execute()
			return result
		else:

#		   # Lista que armazena o grafo
			graph = []
#
#			# Número de nós que foram expandidos
			expandidos = 1

			# Nó inicial
			node = Node(self._problem.initial)
			# Testa se é o objetivo e adiciona esse nó e uma lista vazia no grafo para exibição gráfica
			if self._problem.goal_test(node.state):
				graph.append([node.state, []])
				return node, graph, expandidos

			# fronteira
			frontier = FIFOQueue()

			# adiciona o nó à fronteira
			frontier.append(node)

			# a lista de explorados é um conjunto set() porque os nós não podem se repetir em um grafo
			explored = set()
			# Aqui inicia a procura
			while frontier:
				lista = []  # lista de expandidos

				# É retirado um nó da fronteira
				node = frontier.pop()
				# E adicionado mais um nó nos expandidos

				# É adicionado o nó ao conjunto de explorados (não há repetição de elementos)
				explored.add(node.state)

				# O nó é expandido e se não está na fronteira ou no conjunto de nós explorados
				# é adicionado à fronteira e à lista de nós expandidos
				is_expanded = False

				for child in node.expand(self._problem):
					# if child.state not in explored and child not in frontier:
					if child.state not in lista and child.state not in explored and child.state not in frontier:
						lista.append(child.state)
						explored.add(child.state)
						is_expanded = True
						if self._problem.goal_test(child.state):
							graph.append([node.state, lista])
							return child, graph, expandidos
						frontier.append(child)
				# A lista de nós expandidos acima é adicionado ao grafo
				if is_expanded == True:
					expandidos += 1
				graph.append([node.state, lista])
			return None, graph, expandidos

